package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 112. 路径总和
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 113. 路径总和ii
 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * @author Liyc
 * @date 2024/1/9 14:16
 **/

public class Solution13 {
    /**
     * 112. 路径总和-递归法
     * @param root
     * @param targetsum
     * @return
     */
    public boolean haspathsum1(TreeNode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val;
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) {
            boolean left = haspathsum1(root.left, targetsum);
            if (left) {
                return true;
            }
        }
        if (root.right != null) {
            boolean right = haspathsum1(root.right, targetsum);
            if (right) {
                return true;
            }
        }
        return false;
    }

    /**
     * 112. 路径总和-迭代法
     * @param root
     * @param targetsum
     * @return
     */
    public boolean haspathsum2(TreeNode root, int targetsum) {
        if (root == null) {
            return false;
        }
        Stack<Object> stack = new Stack<>();
        stack.add(root);
        stack.add(root.val);
        while (!stack.isEmpty()) {
            int size = stack.size();
            for (int i = 0; i < size; i++) {
                int value = (Integer)stack.pop();
                TreeNode treeNode = (TreeNode) stack.pop();
                if (treeNode.left == null && treeNode.right == null && value == targetsum) {
                    return true;
                }
                if (treeNode.left != null) {
                    stack.add(treeNode.left);
                    stack.add(value + treeNode.left.val);
                }
                if (treeNode.right != null) {
                    stack.add(treeNode.right);
                    stack.add(value + treeNode.right.val);
                }
            }
        }
        return false;
    }

    /**
     * 0113.路径总和-ii 递归法（迭代法比较麻烦）
     * 113.路径总和ii要遍历整个树，找到所有路径，所以递归函数不要返回值！
     * @param root
     * @param targetsum
     * @return
     */
    public List<List<Integer>> pathsum(TreeNode root, int targetsum) {
        List<List<Integer>> result = new ArrayList<>();
        // 非空判断
        if (root == null) {
            return result;
        }
        List<Integer> path = new ArrayList<>();

        pathValue(root,targetsum,result,path);
        return result;
    }

    public void pathValue(TreeNode treeNode, int targetsum, List<List<Integer>> result, List<Integer> path) {
        path.add(treeNode.val);
        // 遇到了叶子节点
        if (treeNode.left == null && treeNode.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - treeNode.val == 0) {
                result.add(new ArrayList<>(path));
            }
            return;// 如果和不为 targetsum，返回
        }
        if (treeNode.left != null) {
            pathValue(treeNode.left, targetsum - treeNode.val, result, path);
            path.remove(path.size() - 1);// 回溯
        }
        if (treeNode.right != null) {
            pathValue(treeNode.right, targetsum - treeNode.val, result, path);
            path.remove(path.size() - 1);// 回溯
        }
    }
}
